Problem statement: zenit17kkg

Geológia

Počet bodov: 30, časový limit: 1000ms

Geológ Martin sa vybral na výpravu za diamantami. Keďže je vyštudovaným geológom, podarilo sa mu nájsť miesto, kde je v zemi diamantov celá kopa! Teraz by z nich chcel vybrať ten najväčší.

K dispozícii máme plánik s diamantami. Diamant má tvar diamantu (štvorca otočeného o \(45°\)). Zem je označená znakom . a okraj diamantu je označený ako #. Keďže diamanty sú priesvitné, vidíme iba ich okraje. Diamanty sa môžu prekrývať.

Vstup a výstup

V prvom riadku sú dve celé čísla \(1 \leq r,s \leq 400\) – počet riadkov a stĺpcov plániku. Nasleduje \(r\) riadkov, kde v každom riadku je \(s\) znakov – buď . alebo #.

Na výstup vypíšte jedno číslo – dĺžku strany najväčšieho diamantu.

Pozor, časový limit je pomerne tesný. Nie je zaručené, že správne riešenie v pomalšom jazyku dostane plný počet bodov.

Príklady

Input:

5 5
.....
..#..
.#.#.
..#..
.....

Output:

2

Input:

4 3
..#
#..
..#
.#.

Output:

1

Input:

10 10
..#.#.....
.#.#.#....
..#...#...
.#.#...#..
#..#....#.
.#.....#..
..#...#.#.
...#.#...#
.#..#.#.#.
.......#..

Output:

5

Input:

1 1
.

Output:

0